package leetcode._08_dynic;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author pppppp
 * @date 2022/3/24 17:35
 * 给你一个整数数组 nums 和一个整数 target 。
 * 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
 * <p>
 * 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
 * 返
 *
 * <p>
 * 示例 1：
 * 输入：nums = [1,1,1,1,1], target = 3
 * 输出：5
 * 解释：一共有 5 种方法让最终目标和为 3 。
 * -1 + 1 + 1 + 1 + 1 = 3
 * +1 - 1 + 1 + 1 + 1 = 3
 * +1 + 1 - 1 + 1 + 1 = 3
 * +1 + 1 + 1 - 1 + 1 = 3
 * +1 + 1 + 1 + 1 - 1 = 3
 * <p>
 * 示例 2：
 * 输入：nums = [1], target = 1
 * 输出：1
 *  
 * <p>
 * 提示：
 * <p>
 * 1 <= nums.length <= 20
 * 0 <= nums[i] <= 1000
 * 0 <= sum(nums[i]) <= 1000
 * -1000 <= target <= 1000
 */
public class _494_目标和 {

    @Test
    public void T_0() {
        int[][] nums = {
                {0, 0, 0, 0,},
                {1, 2, 1},
                {0, 0, 1},
                {1, 1, 1, 1, 1}, {1}};
        int[] target = {0, 0, 1, 3, 1};
        int[] ans = {16, 2, 4, 5, 1};
        for (int i = 0; i < nums.length; i++) {
            System.out.println(findTargetSumWays(nums[i], target[i]) == ans[i]);
            // System.out.println(findTargetSumWays_0(nums[i], target[i]) == ans[i]);
            // System.out.println(findTargetSumWays_1(nums[i], target[i]) == ans[i]);
        }
    }

    /*1.转化为将数据分为两组求差值是否存在————
        dp[i][j] 表示在数组 i 个数中选取元素，使得这些元素之和等于 j 的方案数。
        当没有任何元素可以选取时，元素和只能是 0，对应的方案数是 1，因此动态规划的边界条件是：
        dp[0][j] = {
                        1,j=0;
                        0,j >= 1;
                    }
        dp[i][j] = dp[i-1][j] 或 dp[i-1][j] + dp[i-1][j-Ni];

    */
    public int findTargetSumWays_gf(int[] nums, int target) {
        int sum = Arrays.stream(nums).sum();
        int diff = sum - target;
        if (diff < 0 || diff % 2 != 0) {
            return 0;
        }
        int n = nums.length, neg = diff / 2;
        int[][] dp = new int[n + 1][neg + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            int num = nums[i - 1];
            for (int j = 0; j <= neg; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= num) {
                    dp[i][j] += dp[i - 1][j - num];
                }
            }
        }
        return dp[n][neg];
    }

    /*0.传统的dp略复杂 分类讨论 判断边界要准确  初始化为0的数时要加倍   转化为和为 [-sum,sum]的 0-1 背包问题 * */
    public int findTargetSumWays(int[] nums, int target) {

        if (nums.length == 1) {
            return target == nums[0] || target == -nums[0] ? 1 : 0;
        }

        int sum = Arrays.stream(nums).sum();
        int[][] dp = new int[nums.length][sum * 2 + 1];

        dp[0][sum - nums[0]]++;
        dp[0][sum + nums[0]]++;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j <= 2 * sum; j++) {
                if (j >= nums[i]) {
                    dp[i][j] += dp[i - 1][j - nums[i]];
                }
                if (j + nums[i] <= 2 * sum) {
                    dp[i][j] += dp[i - 1][j + nums[i]];
                }
                if (i == nums.length - 1 && j == target + sum) {
                    return dp[i][j];
                }
            }
        }
        return 0;
    }

    /*0.1优化 去掉0*/
    public int findTargetSumWays_0(int[] nums, int target) {
        /*去掉0*/
        ArrayList<Integer> list = new ArrayList<>();
        for (int num : nums) {
            if (num != 0) {
                list.add(num);
            }
        }
        int time = 1;
        if (list.size() < nums.length) {
            int[] n = new int[list.size()];
            for (int i = 0; i < list.size(); i++) {
                n[i] = list.get(i);
            }
            time <<= (nums.length - list.size());
            nums = n;
        }

        if (nums.length <= 1) {
            if (nums.length == 1) {
                return target == nums[0] || target == -nums[0] ? time : 0;
            }
            return time;
        }

        int sum = Arrays.stream(nums).sum();
        int[][] dp = new int[nums.length][sum * 2 + 2];

        dp[0][sum - nums[0]]++;
        dp[0][sum + nums[0]]++;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j <= 2 * sum; j++) {
                if (j >= nums[i]) {
                    dp[i][j] += dp[i - 1][j - nums[i]];
                }
                if (j + nums[i] <= 2 * sum) {
                    dp[i][j] += dp[i - 1][j + nums[i]];
                }
                if (i == nums.length - 1 && j == target + sum) {
                    return dp[i][j] * time;
                }
            }
        }
        return 0;
    }

    /*0.2优化 滚动数组 不能优化 会改变值*/
    public int findTargetSumWays_1(int[] nums, int target) {

        if (nums.length == 1) {
            return target == nums[0] || target == -nums[0] ? 1 : 0;
        }

        int sum = Arrays.stream(nums).sum();
        int[] dp = new int[sum * 2 + 1];
        /* +0 -0 */
        dp[sum - nums[0]]++;
        dp[sum + nums[0]]++;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 2 * sum; j >= 0; j--) {
                if (j >= nums[i]) {
                    dp[j] += dp[j - nums[i]];
                }
                if (j + nums[i] <= 2 * sum) {
                    dp[j] += dp[j + nums[i]];
                }
                if (i == nums.length - 1 && j == target + sum) {
                    return dp[j];
                }
            }
        }
        return 0;
    }

}
